def getMap(x,y):
  """
  获取地图 一维数组 方便计算
  """
  map = []
  for i in range(y):
    for j in range(x):
      map.append(0)
  return map

def getPoint(s,e,y,map):
  """
  获取点-路径：
  """
  paths = []

  pathX,pathY = e
  while s[0] != pathX or s[1] != pathY:
    key = pathY * y + pathX
    paths.append([pathX,pathY])
    pathX,pathY = map[key]
    if (pathX,pathY) == tuple(start):
      break
  return paths

def findPath(x,y, start, end, body):
  """
  广度搜索 寻路算法
    -启发式搜索就是通过 点到点的距离 作为启发式函数 并且每次都选择距离最短的点进行搜索
  """
  print("run findPath")
  

  # 1.把起点加入到队列
  queue = [start]

  # 记录上一次的点 这样找到了后才能找到上一个点 输出路径
  lastMap = getMap(x,y)

  
  def insertQueue(iX,iY, lX,lY):
    """
    插入队列
    """
    # 判断是否越界
    if iX < 0 or iX >= x or iY < 0 or iY >= y:
      return False
    
    # 判断是否撞身子
    if [iX,iY] in body:
      return False
    
    # 判断是否已经在队列中
    if [iX,iY] in queue:
      return False
    # print([iX,iY], lX,lY, iY * y + lX)
    # 记录上一个点 是移动后的点 索引 这样才能记住上一个点
    # print("记录上一个点",iX,iY, iY * y + iX, lX,lY)
    # 这里有个坑 不能直接赋值 会导致 所有的都是一个值 因为是有很多条路线 所以后面的可能会替换前面的 需要加个判断
    if lastMap[iY * y + iX] == 0:
      lastMap[iY * y + iX] = [lX,lY]
    queue.append([iX,iY])
    return False

  while len(queue) > 0:
    [iX,iY] = queue.pop(0)

    # 进行广度搜索 逆时针方向  左 上 右 下
    insertQueue(iX - 1, iY, iX, iY)
    insertQueue(iX, iY - 1, iX, iY)
    insertQueue(iX + 1, iY, iX, iY)
    insertQueue(iX, iY + 1, iX, iY)

    

    # 判断是否到达终点
    if iX == end[0] and iY == end[1]:
      return getPoint(start,end,y,lastMap)
      # for i in range(20):
      #   key = pathY * y + pathX
      #   if lastMap[key]:
      #     print(i, lastMap[key])
      #     pathY,pathY = lastMap[key]
      #     if (pathX,pathY) == tuple(start):
      #       print("到达起点")
      #       break
      #     paths.append([pathY,pathY])
      # return paths
  return False

row,col = 10,10

start = [1,2]

end = [5,5]

body = [
  # [1,2],
  [2,2],
]
# points = findPath(row,col, start, end, body)
# print(points)